package 华为OD机试B卷复用题.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ3_欢乐周末 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试B卷复用题/进阶题/input/3.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    // 深度优先基本数组，matrix 保存地图，isVisited 保存是否被访问，M 高度 N 宽度，res 结果
    static int[][] matrix;
    static boolean[][] isVisited;
    static int M = 0, N = 0;
    static int res = 0;
    // 为了优化，如果两个餐厅连通，那么它们要么都能被访问到，要么都不能
    static int[][] canteen;
    static int rootX = 0, rootY = 0;
    // 保存中间变量
    static int count;

    static void Solution(Scanner in) {
        M = in.nextInt();
        N = in.nextInt();
        matrix = new int[M][N];
        isVisited = new boolean[M][N];
        canteen = new int[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 3) {
                    isVisited = new boolean[M][N];
                    rootX = i;
                    rootY = j;
                    count = 0;
                    dfs(i, j);
                }
            }
        }
        System.out.println(res);
    }

    static void dfs(int x, int y) {
        if (count == 2
                || x < 0
                || x >= M
                || y < 0
                || y >= N
                || isVisited[x][y]
                || matrix[x][y] == 1
                || canteen[rootX][rootY] == 1) {
            return;
        }
        isVisited[x][y] = true;
        if (matrix[x][y] == 2) {
            count++;
            if (count == 2) {
                canteen[rootX][rootY] = 1;
                res++;
                return;
            }
        }
        if (matrix[x][y] == 3 && canteen[x][y] == 1) {
            res++;
            canteen[rootX][rootY] = 1;
            return;
        }
        dfs(x - 1, y); // 上
        dfs(x + 1, y); // 下
        dfs(x, y - 1); // 左
        dfs(x, y + 1); // 右
    }
}
